<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  
  
  <title>学习笔记 网络流 | Hexo</title>
  <meta name="viewport" content="width=device-width, initial-scale=1, shrink-to-fit=no">
  <meta name="description" content="网络流（×）网络瘤（√）">
<meta property="og:type" content="article">
<meta property="og:title" content="学习笔记 网络流">
<meta property="og:url" content="http://example.com/2022/02/17/%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0%20%E7%BD%91%E7%BB%9C%E6%B5%81/index.html">
<meta property="og:site_name" content="Hexo">
<meta property="og:description" content="网络流（×）网络瘤（√）">
<meta property="og:locale" content="en_US">
<meta property="og:image" content="https://s2.loli.net/2022/02/15/F1rhiWdu6ARYZ9g.png">
<meta property="og:image" content="https://s2.loli.net/2022/02/15/8YF7ENqLh5a4H26.png">
<meta property="og:image" content="https://s2.loli.net/2022/02/15/8oZWv13OlqfsDId.png">
<meta property="article:published_time" content="2022-02-17T12:13:34.660Z">
<meta property="article:modified_time" content="2023-07-19T11:51:01.607Z">
<meta property="article:author" content="John Doe">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://s2.loli.net/2022/02/15/F1rhiWdu6ARYZ9g.png">
  
    <link rel="alternate" href="/atom.xml" title="Hexo" type="application/atom+xml">
  
  
    <link rel="shortcut icon" href="/favicon.png">
  
  
    
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/typeface-source-code-pro@0.0.71/index.min.css">

  
  
<link rel="stylesheet" href="/css/style.css">

  
    
<link rel="stylesheet" href="/fancybox/jquery.fancybox.min.css">

  
  
<meta name="generator" content="Hexo 6.3.0"></head>

<body>
  <div id="container">
    <div id="wrap">
      <header id="header">
  <div id="banner"></div>
  <div id="header-outer" class="outer">
    <div id="header-title" class="inner">
      <h1 id="logo-wrap">
        <a href="/" id="logo">Hexo</a>
      </h1>
      
    </div>
    <div id="header-inner" class="inner">
      <nav id="main-nav">
        <a id="main-nav-toggle" class="nav-icon"><span class="fa fa-bars"></span></a>
        
          <a class="main-nav-link" href="/">Home</a>
        
          <a class="main-nav-link" href="/archives">Archives</a>
        
      </nav>
      <nav id="sub-nav">
        
        
          <a class="nav-icon" href="/atom.xml" title="RSS Feed"><span class="fa fa-rss"></span></a>
        
        <a class="nav-icon nav-search-btn" title="Search"><span class="fa fa-search"></span></a>
      </nav>
      <div id="search-form-wrap">
        <form action="//google.com/search" method="get" accept-charset="UTF-8" class="search-form"><input type="search" name="q" class="search-form-input" placeholder="Search"><button type="submit" class="search-form-submit">&#xF002;</button><input type="hidden" name="sitesearch" value="http://example.com"></form>
      </div>
    </div>
  </div>
</header>

      <div class="outer">
        <section id="main"><article id="post-学习笔记 网络流" class="h-entry article article-type-post" itemprop="blogPost" itemscope itemtype="https://schema.org/BlogPosting">
  <div class="article-meta">
    <a href="/2022/02/17/%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0%20%E7%BD%91%E7%BB%9C%E6%B5%81/" class="article-date">
  <time class="dt-published" datetime="2022-02-17T12:13:34.660Z" itemprop="datePublished">2022-02-17</time>
</a>
    
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 class="p-name article-title" itemprop="headline name">
      学习笔记 网络流
    </h1>
  

      </header>
    
    <div class="e-content article-entry" itemprop="articleBody">
      
        <p>网络流（×）网络瘤（√）</p>
<h2 id="1-引入"><a href="#1-引入" class="headerlink" title="1.引入"></a>1.引入</h2><p>想象这样一个场景：自来水厂和您家分别坐落在城市的两端。自来水厂可以以任意速率生产水，您家可以以任意速率接受水。您家和自来水厂之间有一些中转站和水管，水管有最大流速限制（即每单位时间最多流多少单位水），中转站不能存水，只能输进多少就马上吐出多少。</p>
<p>这个东西就是网络流。把这个问题数学化就便乘了这样：</p>
<blockquote>
<p>假设 $G(V,E)$ 是一个有限的有向图，它的每条边 $(u,v) \in E$ 都有一个非负值实数的容量 $c(u,v)$ 。如果 $(u,v)$ 不属于 $E$ ，我们假设 $c(u,v) = 0$ 。我们区别两个顶点：一个源点 $s$ 和一个汇点 $t$。一道网络流是一个对于所有结点 $u$ 和 $v$ 都有以下特性的实数函数 $f(u,v)$</p>
<p>容量限制 (Capacity Constraints): $f(u,v)≤c(u,v)$ 一条边的流不能超过它的容量。</p>
<p>斜对称 (Skew Symmetry): $f(u,v)=-f(v,u)$ 由 $u$ 到 $v$ 的净流必须是由 $v$ 到 $u$ 的净流的相反（参考例子）。（既然要看网络流，这是一定要知道的）</p>
<p>流守恒 (Flow Conservation):除非 $u=s$ 或 $u=t$ ，否则 $\sum_{w\in V}f(u,w)=0$ ——结点的净流是零，除了“制造”流的源点和“消耗”流的汇点。</p>
<p>注意 $f(u,v)$ 是由 $u$ 到 $v$ 的净流。如果该图代表一个实质的网络，由 $u$ 到$v$ 有 $4$ 单位的实际流及由 $v$ 到 $u$ 有 $3$ 单位的实际流，那么$f(u,v) = 1$ 及 $f(v,u) = − 1$ 。</p>
<p>以上内容摘自百度百科 链接：[<a target="_blank" rel="noopener" href="https://baike.baidu.com/item/%E7%BD%91%E7%BB%9C%E6%B5%81/2987528">https://baike.baidu.com/item/%E7%BD%91%E7%BB%9C%E6%B5%81/2987528</a>]</p>
</blockquote>
<h2 id="2-最大流"><a href="#2-最大流" class="headerlink" title="2.最大流"></a>2.最大流</h2><p>您观察了这个宏伟的管道系统，想问一个问题：您家最多能以多大的速率用水？（即：找到一个流函数 $f$，使得 $\sum_{w\in V} f(w,t)$ 最大）这就是最大流问题。</p>
<h3 id="2-1-Ford-Fulkerson-算法"><a href="#2-1-Ford-Fulkerson-算法" class="headerlink" title="2.1.Ford-Fulkerson 算法"></a>2.1.Ford-Fulkerson 算法</h3><p>一个简单的想法是每次从源点到汇点找一条路径，再把这条路径上的每条边的剩余容量减去这条路径上的“瓶颈”（即最小流量），每条边的反向边的剩余容量加上“瓶颈”（方便反悔）。（这种路径被称为增广路，找增广路之后的图被称为残量网络）这就是 Ford-Fulkerson 算法。</p>
<p>然而，可以构造这样一个图，使得它跑得贼慢：</p>
<p><img src="https://s2.loli.net/2022/02/15/F1rhiWdu6ARYZ9g.png" alt="屏幕截图 2022-02-15 133918.png"></p>
<p><img src="https://s2.loli.net/2022/02/15/8YF7ENqLh5a4H26.png" alt="屏幕截图 2022-02-15 133939.png"></p>
<p><img src="https://s2.loli.net/2022/02/15/8oZWv13OlqfsDId.png" alt="屏幕截图 2022-02-15 133942.png"></p>
<p>容易发现，中间的那条边会被反复增广再反悔。有没有什么办法避免这种情况？</p>
<h3 id="2-2-Edmond-Karp-算法"><a href="#2-2-Edmond-Karp-算法" class="headerlink" title="2.2.Edmond-Karp 算法"></a>2.2.Edmond-Karp 算法</h3><p>一个想法是每次通过 BFS 找到源点到汇点的最短路进行增广，这就是 Edmond-Karp 算法的思想。它的时间复杂度为 $O(nm^2)$，但一般跑不满。</p>
<p>代码如下：<br><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="type">bool</span> <span class="title">bfs</span><span class="params">()</span></span>&#123;<span class="comment">//BFS找增广路</span></span><br><span class="line">    <span class="built_in">memset</span>(pre,<span class="number">0</span>,<span class="built_in">sizeof</span>(pre));</span><br><span class="line">    <span class="built_in">memset</span>(dis,<span class="number">0</span>,<span class="built_in">sizeof</span>(dis));</span><br><span class="line">    <span class="built_in">memset</span>(vis,<span class="number">0</span>,<span class="built_in">sizeof</span>(vis));</span><br><span class="line">    queue&lt;<span class="type">int</span>&gt; q;</span><br><span class="line">    q.<span class="built_in">push</span>(s);</span><br><span class="line">    dis[s]=INF;vis[s]=<span class="literal">true</span>;</span><br><span class="line">    <span class="keyword">while</span>(q.<span class="built_in">size</span>())&#123;</span><br><span class="line">        <span class="type">int</span> u=q.<span class="built_in">front</span>();</span><br><span class="line">        q.<span class="built_in">pop</span>();</span><br><span class="line">        <span class="keyword">if</span>(u==t)<span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i=g.head[u];i!=<span class="number">0</span>;i=g.g[i].next)&#123;</span><br><span class="line">            <span class="type">int</span> v=g.g[i].v,&amp;w=g.g[i].w;</span><br><span class="line">            <span class="keyword">if</span>(w&amp;&amp;!vis[v])&#123;</span><br><span class="line">                dis[v]=<span class="built_in">min</span>(dis[u],w);</span><br><span class="line">                pre[v]=i;<span class="comment">//记录增广路</span></span><br><span class="line">                q.<span class="built_in">push</span>(v);</span><br><span class="line">                vis[v]=<span class="literal">true</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">Edmonds_Karp</span><span class="params">()</span></span>&#123;</span><br><span class="line">    <span class="type">int</span> res=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">while</span>(<span class="built_in">bfs</span>())&#123;</span><br><span class="line">        <span class="type">int</span> now=t;</span><br><span class="line">        <span class="keyword">while</span>(now!=s)&#123;</span><br><span class="line">            g.g[pre[now]].w-=dis[t];</span><br><span class="line">            g.g[pre[now]^<span class="number">1</span>].w+=dis[t];<span class="comment">//一个小技巧，把边和反向边在数组中成对存储，^1之后的编号就是反向边的编号。</span></span><br><span class="line">            now=g.g[pre[now]^<span class="number">1</span>].v;</span><br><span class="line">        &#125;</span><br><span class="line">        res+=dis[t];</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<h3 id="2-3-Dinic-算法"><a href="#2-3-Dinic-算法" class="headerlink" title="2.3.Dinic 算法"></a>2.3.Dinic 算法</h3><p>Edmond-Karp 算法虽然效率较高，但能不能再优化一下呢？当然能！</p>
<p>还有一个想法是先按照到源点的距离在图上“分层”，再用 DFS 找增广路，找增广路时强制只能从上一层走到下一层。这就是 Dinic 算法。具体细节请参照代码：</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">int</span> level[MAXN+<span class="number">5</span>];<span class="comment">//记录每一个点的层次</span></span><br><span class="line"><span class="function"><span class="type">bool</span> <span class="title">bfs</span><span class="params">()</span></span>&#123;<span class="comment">//分层</span></span><br><span class="line">    <span class="built_in">memset</span>(level,<span class="number">0</span>,<span class="built_in">sizeof</span>(level));</span><br><span class="line">    queue&lt;<span class="type">int</span>&gt; q;</span><br><span class="line">    q.<span class="built_in">push</span>(s);</span><br><span class="line">    level[s]=<span class="number">1</span>;</span><br><span class="line">    <span class="keyword">while</span>(q.<span class="built_in">size</span>())&#123;</span><br><span class="line">        <span class="type">int</span> u=q.<span class="built_in">front</span>();</span><br><span class="line">        q.<span class="built_in">pop</span>();</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i=g.head[u];i;i=g.g[i].next)&#123;</span><br><span class="line">            <span class="type">int</span> v=g.g[i].v,w=g.g[i].w;</span><br><span class="line">            <span class="keyword">if</span>(w&gt;<span class="number">0</span>&amp;&amp;level[v]==<span class="number">0</span>)&#123;</span><br><span class="line">                level[v]=level[u]+<span class="number">1</span>;</span><br><span class="line">                q.<span class="built_in">push</span>(v);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span>(level[t])<span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">    <span class="keyword">else</span> <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">dfs</span><span class="params">(<span class="type">int</span> u,<span class="type">int</span> dis)</span></span>&#123;<span class="comment">//找增广路</span></span><br><span class="line">    <span class="keyword">if</span>(u==t)&#123;</span><br><span class="line">        <span class="keyword">return</span> dis;</span><br><span class="line">    &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">        <span class="type">int</span> out=<span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i=g.head[u];i;i=g.g[i].next)&#123;</span><br><span class="line">            <span class="type">int</span> v=g.g[i].v,&amp;w=g.g[i].w;</span><br><span class="line">            <span class="keyword">if</span>(w&gt;<span class="number">0</span>&amp;&amp;level[v]==level[u]+<span class="number">1</span>)&#123;</span><br><span class="line">                <span class="type">int</span> nxt=<span class="built_in">dfs</span>(v,<span class="built_in">min</span>(w,dis));</span><br><span class="line">                <span class="keyword">if</span>(nxt)&#123;</span><br><span class="line">                    w-=nxt;</span><br><span class="line">                    g.g[i^<span class="number">1</span>].w+=nxt;</span><br><span class="line">                    dis-=nxt;</span><br><span class="line">                    out+=nxt;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span>(out==<span class="number">0</span>)level[u]=<span class="number">-1</span>;<span class="comment">//如果当前点被榨干了就撇了它</span></span><br><span class="line">        <span class="keyword">return</span> out;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">Dinic</span><span class="params">()</span></span>&#123;</span><br><span class="line">    <span class="type">int</span> res=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">while</span>(<span class="built_in">bfs</span>())&#123;</span><br><span class="line">        <span class="keyword">while</span>(<span class="type">int</span> tmp=<span class="built_in">dfs</span>(s,INF))&#123;</span><br><span class="line">            res+=tmp;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="3-费用流"><a href="#3-费用流" class="headerlink" title="3.费用流"></a>3.费用流</h2><p>现在自来水公司要对每条水管收费了。每条水管都有一个价格，每流一滴水都要收若干块钱。现在您想问，如果您家以最大的速率用水，您一个单位时间最少要花多少钱？</p>
<p>一个简单的想法是每次按价格跑一遍 SPFA，再沿最短路增广，重复增广知道找不到增广路为止。</p>
<p>代码：</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">int</span> dis[MAXN+<span class="number">5</span>],flow[MAXN+<span class="number">5</span>];</span><br><span class="line"><span class="type">int</span> pre[MAXN+<span class="number">5</span>];</span><br><span class="line"><span class="function"><span class="type">bool</span> <span class="title">SPFA</span><span class="params">()</span></span>&#123;</span><br><span class="line">    <span class="built_in">memset</span>(dis,<span class="number">0x3f</span>,<span class="built_in">sizeof</span>(dis));</span><br><span class="line">    <span class="built_in">memset</span>(flow,<span class="number">0</span>,<span class="built_in">sizeof</span>(flow));</span><br><span class="line">    dis[s]=<span class="number">0</span>;</span><br><span class="line">    flow[s]=<span class="number">0x3f3f3f3f</span>;</span><br><span class="line">    queue&lt;<span class="type">int</span>&gt; q;</span><br><span class="line">    q.<span class="built_in">push</span>(s);</span><br><span class="line">    <span class="keyword">while</span>(q.<span class="built_in">size</span>())&#123;</span><br><span class="line">        <span class="type">int</span> u=q.<span class="built_in">front</span>();</span><br><span class="line">        q.<span class="built_in">pop</span>();</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i=head[u];i;i=g[i].nxt)&#123;</span><br><span class="line">            <span class="type">int</span> v=g[i].v,w=g[i].w,c=g[i].c;</span><br><span class="line">            <span class="keyword">if</span>(w&amp;&amp;dis[u]+c&lt;dis[v])&#123;</span><br><span class="line">                dis[v]=dis[u]+c;</span><br><span class="line">                flow[v]=<span class="built_in">min</span>(flow[u],w);</span><br><span class="line">                pre[v]=i;</span><br><span class="line">                q.<span class="built_in">push</span>(v);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> dis[t]!=<span class="number">0x3f3f3f3f</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function">pair&lt;<span class="type">int</span>,<span class="type">int</span>&gt; <span class="title">SSP</span><span class="params">()</span></span>&#123;</span><br><span class="line">    <span class="type">int</span> max_flow=<span class="number">0</span>,cost=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">while</span>(<span class="built_in">SPFA</span>())&#123;</span><br><span class="line">        <span class="type">int</span> u=t;</span><br><span class="line">        <span class="keyword">while</span>(u!=s)&#123;</span><br><span class="line">            <span class="type">int</span> t1=pre[u];</span><br><span class="line">            g[t1].w-=flow[t];</span><br><span class="line">            g[t1^<span class="number">1</span>].w+=flow[t];</span><br><span class="line">            u=g[t1^<span class="number">1</span>].v;</span><br><span class="line">        &#125;</span><br><span class="line">        max_flow+=flow[t];</span><br><span class="line">        cost+=flow[t]*dis[t];</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="built_in">make_pair</span>(max_flow,cost);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="4-结尾"><a href="#4-结尾" class="headerlink" title="4.结尾"></a>4.结尾</h2><p>网络流的题目主要考察的其实不是网络流算法本身，而是如何建模。建议做一做网络流24题来练习。</p>

      
    </div>
    <footer class="article-footer">
      <a data-url="http://example.com/2022/02/17/%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0%20%E7%BD%91%E7%BB%9C%E6%B5%81/" data-id="clk9o8ln5000a8wi55i0igz33" data-title="学习笔记 网络流" class="article-share-link"><span class="fa fa-share">Share</span></a>
      
      
      
    </footer>
  </div>
  
    
<nav id="article-nav">
  
    <a href="/2022/05/18/%E9%A2%98%E8%A7%A3%20AcWing%202236.%20%E4%BC%8A%E5%9F%BA%E7%9A%84%E6%95%85%E4%BA%8B%20I%20-%20%E9%81%93%E8%B7%AF%E9%87%8D%E5%BB%BA/" id="article-nav-newer" class="article-nav-link-wrap">
      <strong class="article-nav-caption">Newer</strong>
      <div class="article-nav-title">
        
          题解 AcWing 2236. 伊基的故事 I - 道路重建
        
      </div>
    </a>
  
  
    <a href="/2022/02/14/%E9%A2%98%E8%A7%A3%20%E6%B4%9B%E8%B0%B7%20P1763%20%E5%9F%83%E5%8F%8A%E5%88%86%E6%95%B0/" id="article-nav-older" class="article-nav-link-wrap">
      <strong class="article-nav-caption">Older</strong>
      <div class="article-nav-title">题解 洛谷 P1763 埃及分数</div>
    </a>
  
</nav>

  
</article>


</section>
        
          <aside id="sidebar">
  
    

  
    

  
    
  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Archives</h3>
    <div class="widget">
      <ul class="archive-list"><li class="archive-list-item"><a class="archive-list-link" href="/archives/2023/07/">July 2023</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2022/10/">October 2022</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2022/05/">May 2022</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2022/02/">February 2022</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2022/01/">January 2022</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2021/08/">August 2021</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2021/07/">July 2021</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2021/06/">June 2021</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2020/08/">August 2020</a></li></ul>
    </div>
  </div>


  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Recent Posts</h3>
    <div class="widget">
      <ul>
        
          <li>
            <a href="/2023/07/17/%E5%86%B3%E7%AD%96%E5%8D%95%E8%B0%83%E6%80%A7%E4%BC%98%E5%8C%96DP%20%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0%20AND%20P4767%20%E3%80%8CIOI2000%E3%80%8D%20%E9%82%AE%E5%B1%80%20%E9%A2%98%E8%A7%A3/">决策单调性优化DP 学习笔记 AND P4767 「IOI2000」 邮局 题解</a>
          </li>
        
          <li>
            <a href="/2022/10/30/CSP-S%202022%20%E6%B8%B8%E8%AE%B0/">CSP-S 2022 游记</a>
          </li>
        
          <li>
            <a href="/2022/05/29/%E6%96%9C%E7%8E%87%E4%BC%98%E5%8C%96%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%20%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/">斜率优化动态规划 学习笔记</a>
          </li>
        
          <li>
            <a href="/2022/05/22/PKUSC%E4%B8%80%E5%8F%A5%E8%AF%9D%E6%B8%B8%E8%AE%B0/">PKUSC一句话游记</a>
          </li>
        
          <li>
            <a href="/2022/05/18/%E7%9C%81%E9%80%89%E6%B8%B8%E8%AE%B0%EF%BC%9F%E7%9C%81%E9%80%89%E6%B8%B8%E5%AF%84%EF%BC%81/">省选游记？省选游寄！</a>
          </li>
        
      </ul>
    </div>
  </div>

  
</aside>
        
      </div>
      <footer id="footer">
  
  <div class="outer">
    <div id="footer-info" class="inner">
      
      &copy; 2023 John Doe<br>
      Powered by <a href="https://hexo.io/" target="_blank">Hexo</a>
    </div>
  </div>
</footer>

    </div>
    <nav id="mobile-nav">
  
    <a href="/" class="mobile-nav-link">Home</a>
  
    <a href="/archives" class="mobile-nav-link">Archives</a>
  
</nav>
    


<script src="/js/jquery-3.6.4.min.js"></script>



  
<script src="/fancybox/jquery.fancybox.min.js"></script>




<script src="/js/script.js"></script>





  </div>
</body>
</html>